package com.lhcai.nk.medium;

/**
 * @author lhcstart
 * @create 2023-02-11 19:31
 */

import java.util.Scanner;

/**
 * 动态规划
 */
public class HJ16 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();//总个数
        int N = sc.nextInt();//总钱数

        //获取goods数组
        Goods[] goods = new Goods[m];
        //为数组添加元素
        for (int i = 0; i < m; i++) {
            goods[i] = new Goods();
        }

        for (int i = 0; i < m; i++) {
            int v = sc.nextInt();//价格
            int p = sc.nextInt();//重要度
            int q = sc.nextInt();
            goods[i].v = v;
            goods[i].p = p * v;//直接是p*v 方便计算

            if (q == 0) {
                goods[i].main = true;
            } else if (goods[q - 1].a1 == -1) {
                goods[q - 1].a1 = i;
            } else {
                goods[q - 1].a2 = i;
            }
        }

        int[][] dp = new int[m + 1][N + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= N; j++) {
               //将上一个格子的值赋给本格子
                dp[i][j] =dp[i-1][j];

                if (!goods[i - 1].main) {
                    continue;
                }
                //仅有一主件
                if (j >= goods[i - 1].v) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods[i - 1].v] + goods[i - 1].p);
                }
                //一主件一附件
                if (goods[i - 1].a1 != -1 && j >= goods[i - 1].v + goods[goods[i - 1].a1].v) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods[i - 1].v - goods[goods[i - 1].a1].v] + goods[i - 1].p + goods[goods[i - 1].a1].p);
                }
                //一主件一附件
                if (goods[i - 1].a2 != -1 && j >= goods[i - 1].v + goods[goods[i - 1].a2].v) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods[i - 1].v - goods[goods[i - 1].a2].v] + goods[i - 1].p + goods[goods[i - 1].a2].p);
                }
                //一主件二附件
                if (goods[i - 1].a1 != -1 && goods[i - 1].a2 != -1 && j >= goods[i - 1].v + goods[goods[i - 1].a1].v + goods[goods[i - 1].a2].v) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods[i - 1].v - goods[goods[i - 1].a1].v - goods[goods[i - 1].a2].v] + goods[i - 1].p  + goods[goods[i - 1].a1].p + goods[goods[i - 1].a2].p);
                }
            }
        }

        System.out.println(dp[m][N]);
    }
}

class Goods {
    int v;
    int p;
    boolean main = false;//是否为主件

    int a1 = -1;//定义附件一编号
    int a2 = -1;//定义附件二编号
}